package leetcode;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by Ghost on 2014/12/6.
 */
public class _3Sum {
    public List<List<Integer>> threeSum(int[] num) {
        List<List<Integer>> rst = new LinkedList<List<Integer>>();
        if(num==null || num.length<3)
            return rst;

        Arrays.sort(num);
        for(int i=0;i<num.length-1;i++){
            if(i>0 && num[i]==num[i-1])
                continue;
            int left = i+1,right = num.length-1;
            while(left<right){
                int tmp = 0-num[i];
                if(tmp==num[left]+num[right]){
                    List<Integer> t = new LinkedList<Integer>();
                    t.add(num[i]);
                    t.add(num[left]);
                    t.add(num[right]);
                    rst.add(t);
                    left++;
                    while(left<num.length && num[left]==num[left-1])
                        left++;
                    right--;
                    while(right>=0 && num[right]==num[right+1])
                        right--;
                }
                else if(tmp>num[left]+num[right]){
                    left++;
                    while(left<num.length && num[left]==num[left-1])
                        left++;
                }else{
                    right--;
                    while(right>=0 && num[right]==num[right+1])
                        right--;
                }
            }
        }
        return rst;
    }

    public static void main(String[] args){
        _3Sum sum = new _3Sum();
        int[] num = {-2,0,0,2,2};
        List<List<Integer>> rst = sum.threeSum(num);
        System.out.print(rst);

    }
}
